package com.wuxuan.algorithm_homework.dfsAndBfs;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 深度优先搜索 DFS II
 */
public class DFS2 {

    /**
     * 1.子集(Subset)
     * 给你一个整数数组 nums数组中的元素 互不相同 。返回该数组所有可能的子集。
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
     *
     * 假设数组的长度为 n
     * 时间复杂度: O(n * 2^n)
     * 空间复杂度: O(n * 2^n)
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        findSubsets(nums, 0, new ArrayList<>(), result);

        return result;
    }

    private void findSubsets(int[] nums, int index, List<Integer> cur, List<List<Integer>> result) {
        if (index == nums.length) {
            //注意，这里要new一个！！！不可以直接add(cur),否则之后result里面的List<Integer>都共用一个cur
            result.add(new ArrayList<>(cur));
            //注意，已经到末尾了，直接return！
            return;
        }

        //不选择当前元素
        findSubsets(nums, index + 1, cur, result);

        //选择当前元素
        cur.add(nums[index]);
        findSubsets(nums, index + 1, cur, result);

        //回溯,还原之前节点的状态
        cur.remove(cur.size() - 1);
    }

    @Test
    public void testSubsets() {
        //示例 1:
        //输入:nums =[1,2,3]
        //输出:[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
        List<List<Integer>> result1 = subsets(new int[]{1, 2, 3});
        System.out.println(result1);
        //示例 2:
        //输入:nums =[0]
        //输出:[[], [0]]
        List<List<Integer>> result2 = subsets(new int[]{0});
        System.out.println(result2);
    }

    /**
     * 2.子集 II
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集。
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     *
     * duplicate:重复
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDuplicates(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        //排序，让相同的元素相邻
        Arrays.sort(nums);
        findSubsetsWithDuplicates(nums, 0, false, new ArrayList<>(), result);

        return result;
    }

    private void findSubsetsWithDuplicates(int[] nums, int index, boolean preSelected, List<Integer> cur, List<List<Integer>> result) {
        if (index == nums.length) {
            result.add(new ArrayList<>(cur));
            return;
        }

        //不选择当前
        findSubsetsWithDuplicates(nums, index + 1, false, cur, result);

        //相比上一题，需要额外判断，当前元素和上个元素是否相同,如果相同且上个元素没有选择，则直接返回！否则会有重复的子集！
        if (!preSelected && index > 0 && nums[index] == nums[index - 1]) {
            return;
        }

        //选择当前
        cur.add(nums[index]);
        findSubsetsWithDuplicates(nums, index + 1, true, cur, result);

        //回溯
        cur.remove(cur.size() - 1);

    }

    @Test
    public void testSubsetsWithDuplicates() {
        // 示例 1:
        // 输入:nums =[1,2,2]
        // 输出:[[], [2], [2, 2], [1], [1, 2], [1, 2, 2]]
        List<List<Integer>> result1 = subsetsWithDuplicates(new int[]{1, 2, 2});
        System.out.println(result1);

        // 示例 2:
        // 输入:nums =[0]
        // 输出:[[], [0]]
        List<List<Integer>> result2 = subsetsWithDuplicates(new int[]{0});
        System.out.println(result2);

        // nums: 2222
        // 子集:[[], [2], [2, 2], [2, 2, 2], [2, 2, 2, 2]]
        // ENN
        // NN
        // [2,2]
        // [2,2,2][2,2]
        // [2,2, 2].[2, 2,2, 2]
        // 核心区别:对于相同的元素，如果前面的元素没有被选，直接返回
        List<List<Integer>> result3 = subsetsWithDuplicates(new int[]{2, 2, 2, 2});
        System.out.println(result3);
    }

    /**
     * 3.复原 IP 地址
     * 有效 IP 地址 正好由四个整数(每个整数位于0到 255 之间组成，且不能含有前导 0)，整数之间用分隔。
     * 例如:"0.1.2.201"和"192.168.1.1”是有效 IP 地址，
     * 但是"0.011.255.245"、"192.168.1.312"和“192.168@1.1”是无效 IP 地址。
     *
     * 给定一个只包含数字的字符串 s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在s 中插入 '.’ 来形成。
     * 你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
     *
     * 时间复杂度: O(1), 3 * 3 * 3 * 3 = O(81) = O(1)
     * 空间复杂度: O(1)
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return result;
        }
        dfs(s, 0, 0, "", result);

        return result;
    }

    private void dfs(String s, int index, int segment, String path, List<String> result) {
        if (segment == 4) {
            if (index == s.length()) {
                //把最后一个.去掉！
                result.add(path.substring(0, path.length() - 1));
            }
            return;
        }

        //剪枝优化
        int numCharLeft = s.length() - index;
        if (numCharLeft < (4 - segment) || numCharLeft > 3 * (4 - segment)) {
            return;
        }

        //尝试截取 1 - 3个字符成为一个segment
        for (int i = 1; i <= 3 && index + i <= s.length(); i++) {
            String str = s.substring(index, index + i);
            if (isValid(str)) {
                dfs(s, index + i, segment + 1, path + str + ".", result);
            }
        }
    }

    private boolean isValid(String s) {
        if (s.length() > 1 && s.charAt(0) == '0') {
            return false;
        }

        int num = Integer.parseInt(s);
        return num >= 0 && num <= 255;
    }

    @Test
    public void testRestoreIpAddresses() {
        //示例 1:
        //输入:s="25525511135"
        //输出:[255.255.11.135, 255.255.111.35]
        List<String> result1 = restoreIpAddresses("25525511135");
        System.out.println(result1);

        //示例 2:
        //输入:s="0000"
        //输出:[0.0.0.0]
        List<String> result2 = restoreIpAddresses("0000");
        System.out.println(result2);

        //示例 3:
        //输入:s="101023"
        //输出:[1.0.10.23, 1.0.102.3, 10.1.0.23, 10.10.2.3, 101.0.2.3]
        List<String> result3 = restoreIpAddresses("101023");
        System.out.println(result3);


    }

}
